package com.ch.贪心;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author chenhong
 * @version 1.0.0
 * @ClassName N452.java
 * @Description TODO
 * @createTime 2021年04月11日 17:43:00
 */
public class N452 {
    public static void main(String[] args) {
        int [][]a = {{9,12},{1,10},{4,11},{8,12},{3,9},{6,9},{6,7}};
        Solution452 s = new Solution452();
        int b = s.findMinArrowShots(a);
        System.out.println(b);
    }
}
//从左端排序
class Solution452 {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0)
            return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    if(o1[1] <0 && o2[1] > 0)
                        return -1;
                    if(o1[1] >0 && o2[1]<0)
                        return 1;
                    return o1[1] - o2[1];
                }
                if(o1[0] <0 && o2[0] > 0)
                    return -1;
                if(o1[0] >0 && o2[0]<0)
                    return 1;
                return o1[0] - o2[0];
            }
        });
        int ret = 1;
        //第一个点的尾
        int end = points[0][1];
        for (int[] point : points) {
            if(point[0] > end){
                ret ++;
                end = point[1];
            }else if(point[1] < end){
                end = point[1];
            }
        }
        return ret;
    }
}



//从右端排序
class Solution452_2 {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0)
            return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
               if(o1[1] > o2[1])
                   return 1;
               if(o1[1] < o2[1])
                   return -1;
               return 0;
            }
        });
        int ret = 1;
        //第一个点的尾
        int end = points[0][1];
        for (int[] point : points) {
            if(point[0] > end){
                ret ++;
                end = point[1];
            }
        }
        return ret;
    }
}

